package daily.kou2022_0228;

import java.util.LinkedList;
import java.util.Queue;

//662. 二叉树最大宽度
public class Num662_widthOfBinaryTree {
    public int widthOfBinaryTree(TreeNode root) {
        if (root==null){
            return 0;
        }
        int maxWidth = 0;
        Queue<NodeWithNum> queue = new LinkedList<>();
        queue.offer(new NodeWithNum(root,1));
        while (!queue.isEmpty()){
            int levelWidth = 0;
            //当前队列中该层元素个数
            int size = queue.size();
            //最左侧节点的编号
            int L=0;
            //最右侧节点的编号
            int R=0;
            for (int i = 0; i < size; i++) {
                NodeWithNum cur = queue.poll();
                if (i==0){
                    //node就是最左侧节点
                    L=cur.num;
                }
                if (i==size-1){
                    // 此时node就是该层的最后侧节点
                    R=cur.num;
                }
                if (cur.node.left!=null){
                    queue.offer(new NodeWithNum(cur.node.left,cur.num*2));

                }
                if (cur.node.right!=null){
                    queue.offer(new NodeWithNum(cur.node.right,cur.num*2+1));
                }

            }
            levelWidth=R-L+1;
            maxWidth = Math.max(levelWidth,maxWidth);

        }

        return maxWidth;



    }
        private class NodeWithNum{
        TreeNode node;
        //该节点的编号
        int num;

        public NodeWithNum(TreeNode node, int num) {
            this.node = node;
            this.num = num;
        }
    }






//    public int widthOfBinaryTree(TreeNode root) {
//        if (root==null){
//            return 0;
//        }
//        //存储最大宽度
//        int maxWidth = 0;
//        Queue<NodeWithNum> queue = new LinkedList<>();
//        queue.offer(new NodeWithNum(root,1));
//        while (!queue.isEmpty()){
//            int levelWidth = 0;
//            //当前层元素个数
//            int size= queue.size();
//            // 最左侧的节点编号
//            int L = 0;
//            // 最右侧的节点编号
//            int R = 0;
//            for (int i = 0; i < size; i++) {
//                NodeWithNum cur = queue.poll();
//                if (i==0){
//                    //该节点为最左侧节点
//                    L=cur.num;
//                }
//                if (i==size-1){
//                    //该节点为最右侧节点
//
//                    R=cur.num;
//                }
//                if (cur.node.left!=null){
//                    //入队
//                    queue.offer(new NodeWithNum(cur.node.left,cur.num*2));
//
//                }
//                if (cur.node.right != null) {
//                    queue.offer(new NodeWithNum(cur.node.right, cur.num * 2 + 1));
//                }
//
//            }
//            levelWidth=R-L+1;
//            maxWidth=Math.max(levelWidth,maxWidth);
//
//
//        }
//        return maxWidth;
//
//    }
//    private class NodeWithNum{
//        TreeNode node;
//        //该节点的编号
//        int num;
//
//        public NodeWithNum(TreeNode node, int num) {
//            this.node = node;
//            this.num = num;
//        }
//    }
//





}
